#ifndef __SUBSET_H__
#define __SUBSET_H__
#include <vector>
using namespace std;

/*
* leetcode 78 子集
* 子集问题和组合问题的最大区别, 在于结果的收集
* 
* 例如: 求 {1, 2, 3} 的子集
* 结果: {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {}
* 树形结构如下:
*			{}-123
*	{1}-23		{2}-3		{3}
* {12}-3 {13}	{23}
* {123}
*
* 如上述树形结构, 和组合问题非常相似 (组合总和 II, 穷举所有集合)
* 
* 可以看到, 每个节点就是子集中的一部分, 在树形结构的每一个节点中
* 那么在收集结果的时机上, 不同于 组合和分割 的在终止时收集, 而是在 每层递归(每个节点) 上去收集结果
*/
void BackTrackingSubSets(const vector<int>& set, vector<int>& path, vector<vector<int>>& results, int startIndex = 0) {
	//收集节点
	results.push_back(path);

	if (startIndex == set.size())
		return;

	for (int i = startIndex; i < set.size(); i++) {
		path.push_back(set[i]);
		BackTrackingSubSets(set, path, results, i + 1);
		path.pop_back();
	}
}

/*
* leetcode 90 子集 II
* 需要进行元素去重, 可以参考 组合总和 III
* 
* 大致步骤: 对集合进行排序 -> 树层去重
*/
void BackTrackingSubSetsII(const vector<int>& set, vector<int>& path, vector<vector<int>>& results, vector<bool>& bUsed, int startIndex = 0) {
	results.push_back(path);

	if (startIndex == set.size())
		return;

	for (int i = startIndex; i < set.size(); i++) {
		/*
		* 当该元素的前一个元素的 bUsed 为 false 时, 则可以判断为树层
		*				 若为 true 时, 则是树枝, 不能进行去重
		*/
		if (i > 0 && !bUsed[i - 1] && set[i] == set[i - 1])
			continue;

		path.push_back(set[i]);
		bUsed[i] = true;
		BackTrackingSubSetsII(set, path, results, bUsed, i + 1);
		path.pop_back();
		bUsed[i] = false;
	}
}

#endif // !__SUBSET_H__

